Educational Codeforces Round 153 (Rated for Div. 2)

Not a Substring

构造题。如果 \(s\) 中存在连续相同的括号，则可以构造交替出现的括号；如果 \(s\) 是交替出现的括号，那么就构造连续的括号，此时包含的唯一交替的括号就是 \(()\)，特判一下即可。

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = false;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            ok = true;
            break;
        }
    }
    if (new String(s).equals("()")) {
        io.println("NO");
        return;
    }
    io.println("YES");
    if (ok) io.println("()".repeat(n));
    else io.println("(".repeat(n) + ")".repeat(n));
}

Fancy Coins

数学题。假设最终使用 \(x\) 枚价值为 \(1\) 的硬币，\(y\) 枚价值为 \(k\) 的硬币。如果 \(x\) 大于等于 \(k\)，我们总是将其合成为价值为 \(k\) 的硬币，所以可以保证 \(x\) 小于 \(k\)。显然 \(x=m\bmod k\)，\(y=\frac{m}{k}\)。那么需要补充多少花色硬币呢？易知，需要补充 \(\max(0,x-a_{1})\) 个价值为 \(1\) 的花色硬币，和 \(\max (0,y-a_{k}-\max (0,\frac{a_{1}-x}{k}))\) 个价值为 \(k\) 的花色硬币。

public static void solve() {
    int m = io.nextInt(), k = io.nextInt(), a1 = io.nextInt(), ak = io.nextInt();
    int ans = Math.max(0, m % k - a1) + Math.max(0, m / k - ak - Math.max(0, a1 - m % k) / k);
    io.println(ans);
}

Game on Permutation

一开始的想法是，如果某个元素左边恰好只有一个小于它的元素，那么该位置就是胜位。然而暴力找每个位置左边比它小的元素个数的时间复杂度是 \(O(n^{2})\)，赛时就不知道怎么优化。其实我们可以知道，给定一个序列，胜位是固定不变的。所以可以考虑维护左边的最小元素（表示下一步是否可以下棋）和最小的胜位（如果大于最小胜位，则当前位必输），然后就可以很方便的模拟出答案。

public static void solve() {
    int n = io.nextInt();
    int[] p = new int[n];
    int ans = 0, min = n + 1, minWin = n + 1;
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt();
        if (min < p[i] && p[i] <= minWin) {
            ans++;
            minWin = Math.min(minWin, p[i]);
        }
        min = Math.min(min, p[i]);
    }
    io.println(ans);
}

Balanced String

不会不会。。o(╥﹏╥)o